package org.shj.algorithm.string;

/**
 * 最大子序列的和问题： 给定一个数组 A[a1, a2, ..., an]，求 一个连续子数组，使得该子数组的和最大。
 * 如果和为负数，则最大为 0，因为空数组是任意数组的子数组。
 * 例如； 1, -2, 3, 10, -4, 7, -22, 5
 * 其最大子序列的和是： 16
 * 其最大子序列是： 3, 10, -4, 7
 *
 */
public class MaxSubSequence {

    public static void main(String[] args){
        int[] numbers = new int[]{1, -2, 3, 10, -4, 7, -22, 5};

        analysis(numbers);
        dongGui(numbers);

    }

    /**
     *  分析法：
     *  1. 得出以 i 结尾的序列的和的数组 p[i]
     *  2. 因为 p[j, i] = p[i] - p[j-1], 所以当 p[j-1] 的值为最小时，
     *     p[j, i] 的值就是最大的。
     *  3. 对 p[i] 进行循环时，一边记录最小的 p[i]值，一边计算 p[i]-min 的值，
     *     保存最大的 p[i] - min 的值，循环一次，即得到最大的子序列的和
     * @param numbers
     */
    public static void analysis(int[] numbers){

        // p 数组中的值： p[i] 表示以 i 为结尾的序列的和
        int[] p = new int[numbers.length];

        for(int i = 0 ; i < numbers.length; i++){
            if(i == 0){
                p[i] = numbers[i];
            }else{
                p[i] = p[i - 1] + numbers[i];
            }
        }

        int min = 0;
        int max = 0;

        for(int i = 0; i < p.length; i++){
            if(p[i] < min){
                min = p[i];
            }
            if(p[i] - min > max){
                max = p[i] - min;
            }
        }

        System.out.println(max);
    }

    /**
     * 动态规化法：
     * 1. 记 S[i] 为以 i 结尾的数组中和最大的子数组的和
     * 2. 则 S[i+1] = max(S[i] + A[i+1], A[i+1])
     * @param numbers
     */
    private static void dongGui(int[] numbers){
        int max = 0;
        int sum = 0;
        for(int i = 0; i < numbers.length; i++){
            if(sum > 0){
                sum += numbers[i];
            }else{
                sum = numbers[i] > 0 ? numbers[i] : 0;
            }

            if(sum > max){
                max = sum;
            }
        }

        System.out.println(max);
    }
}
